The abbreviation ‘PUF’ used herein stands for ‘physically uncloneable function’, also called a ‘physical hash function’. The underlying concept is that of digitizing physical properties of an object and thus obtaining a bit sequence which is associated with the object. In this case, it is desirable for the bit sequences of two different physical objects to be uncorrelated with one another. A simple example for the purpose of illustration is a sheet of paper. When viewed under a microscope, it is possible to see a special fine structure of wood chips or cellulose portions. The structure is measured and is presented as a bit sequence by using a suitable algorithm. This bit sequence is then the PUF associated with the sheet of paper. Another sheet of paper will generally provide a totally different bit sequence, that is to say a bit sequence which is uncorrelated with the bit sequence of the first sheet. The terms “bit sequence” and “bit string” are used synonymously below.
The process of generating a bit sequence (the PUF) from the properties of the physical object is called PUF generation. A main use of PUFs is the production of cryptographic keys for fully electronic or computerized encryption methods. By way of example, it would be possible to use the PUF bit string itself as a cryptographic key. Alternatively, it would be possible—and has particular advantages—to compress the PUF bit string to form a shorter bit string and to use the latter as a cryptographic key. The latter method is usually used for chip cards, where a mechanism for PUF generation is integrated in the electronics of the card. In this way, the PUF generation and the use thereof for key production prevents the key itself from having to be stored on the card, which would present a security risk.
A desirable property of a PUF mechanism is that the same physical object, that is to say the same chip card, for example, results in the same bit sequence each time in the course of fresh PUF generation. This should, in particular, also be true under different ambient conditions, such as temperature, air humidity, brightness, electrical and magnetic field strengths, etc.
This is not the case in general, however. Repeated PUF generation for the same physical object generally delivers different bit sequences. Although the bit sequences are quite similar among one another, they are not absolutely identical to one another. Attempts are made to compensate for this deficit by means of methods of coding theory (error correction).
The procedure in this case is as follows. There is a physical object. At the beginning, the PUF bit sequence A associated with the object is generated. The bit string A is thus the result of the first PUF generation operation. The bit sequence A is considered in the same way as a message in coding theory which needs to be transmitted via a channel that is susceptible to noise, the transmission being expected to involve the occurrence of errors, i.e. the collapse of individual bit entries, that is to say that a zero becomes a one or vice-versa. In coding theory, this problem is countered by providing the message A with a redundancy R and transmitting the code word (A, R). If errors occur during the transmission, they can be corrected using coding theory methods owing to the redundancy R. Following correction, the error-free message word A is obtained again.
The same concept is used in PUF generation. The original PUF value A (the value arising in the first PUF generation operation) is referred to as the true PUF value. From the true PUF value A, an associated redundancy value R is calculated. R is called auxiliary information, and R is intended to be used—at a later time—to successfully reconstruct the true PUF value A.
For the sake of simplicity, it has been assumed in this case that the true PUF value A is that bit string which arises in the very first PUF generation operation. In fact, the true PUF value of a chip card is determined during production in the course of chip personalization, for example. In this case, it is customary to produce a PUF value multiple times or frequently in succession, and to define the mean value or the most frequent value as the true PUF value, for example. Another approach is to schedule a reserve. It is assumed that an 800-bit PUF value is required. However, a 1000-bit PUF value is produced (by way of example) in order to have the reserve. In the factory, the 1000-bit PUF value is then generated multiple times, for example 100 times. Each bit position which is not stable during these 100 generation operations, that is to say does not always show the same bit value, is declared invalid. It is assumed that there are 840 locations at which the same bit value occurred each time during the 100 PUF generation operations. Of these 840 locations, 800 are then selected, for example, and these 800 locations define the true PUF value.
The value R calculated using the coding algorithm is stored. For security reasons, the PUF value A itself is not stored and is therefore also not always available. The reason is that the PUF value A is used directly as a cryptographic key, or a cryptographic key is derived from it. If the PUF value A were easily accessible, it would no longer be possible to consider the associated cryptographic key as secret. During later fresh PUF generation, a new PUF value B is obtained. The value B is generally not identical to A, but differs from A only slightly. The aim is to recover the true PUF value A from the available value B.
This is accomplished by using R and methods of coding theory:B→(B,R)→(A,R)→AThe current and present PUF value B is thus extended by the auxiliary information R, with A, B and R being bit strings. The bit sequence (B,R) is then considered to be an erroneous word within the context of coding theory and the error is then corrected using coding theory. The corrected word (A,R) is obtained. In particular, the true PUF value A is now available.
The task of reconstructing the true PUF value A from the most recently generated and currently present PUF value B succeeds only if B does not differ too greatly from A. In the terminology of coding theory: if not too many errors have occurred during the generation of B, considered relative to the original true PUF value A.
The technical implementation of a PUF governs how greatly a newly generated PUF value B typically differs from the true PUF value A, that is to say how many errors typically need to be corrected. Depending on the technical implementation of the PUF, B will differ from A in fewer than 1% of the positions, for example in 0.3% or 0.6%, or in up to 25%. The more B differs from A on average, the greater and more costly the hardware implementation of the PUF reconstruction algorithm. This also means higher manufacturing costs, and greater space requirement and possibly higher power consumption.
There are several reasons for this. If the intention is to form a 128-bit secret key from the PUF value, for example, then the following parameters are obtained.
The higher the error rate (that is to say the more B differs from A), the longer the bit strings A and B must be in order to result in a secure 128-bit key at the end. If, by way of example, 15% errors occur in B in comparison with A, then A (and hence also B) must be approximately 4000 bits long in order to yield a 128-bit secret key (in the case of 25% errors, approximately 6000 bits would be needed). If only 1% errors occur, A and B would need to be approximately 600 bits long in order likewise to provide a 128-bit secret key. The values and ratios indicated above are calculated by using coding theory, and this calculation is known to a person skilled in the art and therefore does not need to be explained in more detail at this juncture. In the case of an even lower error rate and a shorter cryptographic key to be generated, it would also suffice for A and B to comprise 64 bits each, for example.
The more errors that occur, the more powerful the error correction algorithm used needs to be, and the more complex and hence expensive is the implementation thereof.
In the field of electronic chip cards, methods are usually used in which the PUF is generated by measurements on electronic circuits implemented in silicon, for example transistors. Differences in the manufacturing process for the chips, over which even the manufacturer does not have total control, are responsible for two different chips resulting in PUF strings that they have generated being uncorrelated with one another. This is used to allow different chips to automatically generate different PUFs, which is a basic prerequisite from the point of view of security.
Typically, an error rate of between 1% and 10% can be expected for such circuits. That is to say that the newly generated PUF string B will potentially differ from the true PUF string A in approximately p % of the bit locations, p being a number between 1 and 10. In line with the value p determined by experiments, the appropriate PUF string length and a requisite error correction algorithm are then implemented.
In one example, a 128-bit cryptographic key needs to be extracted from the PUF string A. If p is equal to 1, the PUF string A must then have a length of approximately 600 bits. If p is equal to 10, the PUF string A must have a length of approximately 3000 bits. Furthermore, it is true that when p is equal to 1 it is necessary or suffices to have a simpler error correction algorithm than when p is equal to 10.
As already described above, this problem is currently solved solely by means of methods of coding theory: an appropriate algebraic code is chosen, which is almost always a linear code. For the originally measured PUF bit string A, the associated redundancy value R is calculated using the chosen code. This redundancy value R is then stored—as representative of the PUF string A—in the NVM (nonvolatile memory) of the chip card. A itself is not stored, for security reasons. During fresh PUF generation at a later time, the bit string B is obtained. The redundancy value R and an algorithm from the theory of error-correcting codes (algebraic coding theory) are then used to calculate the value A from B. In other words, B is regarded as an erroneous version of A and the errors are corrected by using R and the error correction algorithm.
In this context, the redundancy R needs to be shorter than A. Since R is stored in the NVM, R is deemed to be more or less public knowledge. A cryptographic key is extracted from A. Let |A| be the bit length of A, and let |R| be the bit length of R. The difference |A|−|R| is then the length of the secret. Furthermore, only a single cryptographic key of this length can be obtained from A.
In one example, the PUF value A is assumed to have a length of 500 bits. The redundancy R is assumed to have 400 bits. It is then possible to derive a 100-bit cryptographic key from A. An obvious way of doing this is to add 5 bits from A modulo 2 each time—that is to say to XOR them—in order to obtain a key bit.
Against this background, there is a need for methods and apparatuses which allow improved PUF generation, for example more quickly or with reduced computation complexities.